package book;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

// 最短路径Dijkstra算法实现代码(使用优先队列)
public class ShortestPathSolutionPQ {

    // 定义顶点的访问状态：
    static final int RED = 2;
    static final int GREEN = 1;
    static final int WHITE = 0;

    // 定义优先队列的节点类
    // 同时实现自定义的比较方法
    class QueueNode implements Comparator<QueueNode> {
        int node, path; // 节点编号，最短路径长度

        public QueueNode(){ }
        
        public QueueNode(int node, int path) {
            this.node = node;
            this.path = path;
        }

        @Override
        public int compare(QueueNode o1, QueueNode o2) {
            return Integer.compare(o1.path, o2.path);
        }        
    }
    
    // dijkstra计算最短路径(使用PriorityQueue)
    public int findAllShortestPath(int n, int[][] edges, int src) {
        // 边权集转邻接表，提高邻接点搜索时的效率
        List<List<Integer>> linkTable = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++)
            linkTable.add(new ArrayList<>());
        for (int i = 0; i < edges.length; i++) 
            linkTable.get(edges[i][0]).add(i);

        // dist[x]: 保存起点到 x 的最短路径长度
        // 初始值为无穷大
        int[] dist = new int[n + 1]; 
        Arrays.fill(dist, Integer.MAX_VALUE);
        // visit[x]表示 x 的访问状态：
        int[] visit = new int[n + 1];

        // 初始时只有起点被访问到，设置路径长度为0
        visit[src] = GREEN;
        dist[src] = 0;

        // 创建分支限界法的关键数据结构：优先队列
        PriorityQueue<QueueNode> pq = new PriorityQueue<>(edges.length + 1, new QueueNode());
        pq.offer(new QueueNode(src, 0));

        // 执行dijkstra搜索最短路径
        while (!pq.isEmpty()) {
            // 从优先队列中取出下一个路径最短顶点
            QueueNode sn = pq.poll();
            int s = sn.node;

            // 过滤掉已经处理过的顶点
            if (visit[s] == RED) continue;

            // 将顶点标记为红点，并作为当前搜索点
            visit[s] = RED;

            // 枚举当前顶点 s 的邻接路径，发现新的路径并更新优先队列
            for (int ei : linkTable.get(s)) {
                // 获取目标邻点及到邻点的路径长度
                int t = edges[ei][1], w = edges[ei][2];
                if (visit[t] != RED) {
                    // 计算从起点经过s到达t的路径长度
                    int d = dist[s] + w;
                    if (d < dist[t]) {
                        // 找到更短路径，加入优先队列
                        dist[t] = d;
                        visit[t] = GREEN;
                        pq.offer(new QueueNode(t, d)); 
                    }
                }
            }
        }

        // 输出结果并返回
        int ans = -1;
        System.out.println("所有的顶点路径信息:");
        for (int i = 1; i <= n; i++) {
            System.out.println("目标顶点 " + i + " -> " + dist[i]);
            ans = Math.max(ans, dist[i]);
        }
        return ans;
    }

    public static void main(String[] args) {
        ShortestPathSolution sln = new ShortestPathSolution();
        int[][] edges = {{1,2,2}, {1,5,8},{1,4,3},{2,3,5},{3,5,1},{4,3,2},{4,5,6}};
        int n = 5, src = 1;
        int ans = sln.findAllShortestPath(n, edges, src);
        System.out.println("搜索完毕，最远顶点路径为：" + ans);
    }
}
